perm filename 28B[00,BGB] blob sn#046272 filedate 1973-06-06 generic text, type T, neo UTF8
~F2
	"The  image  tree is generated one threshold level at a time, starting at the
highest level (branch tips). At each level, the image  is  scanned,  and  the  points
above  the threshold are marked in a scratch array. This scatch array is then scanned
for marked points. When one is found, a contiguity routine is  called,  which  visits
all  marked  points  which can be reached from the start via a connected path.    The
marks are erased by this routine as it goes, and statistics are kept  on  the  region
thus  generated,  such  as the sums of the x and y coordinates of the points, and the
sum of the squares of the x and y coordinates (used  to  compute  the  centerand  the
eccentricity).  A  tree  node is then made up for the region, and the scan for marked
points continues.   A special mark is left in the scratch array for each region. When
this  mark  is  encountered  during the scan at the next level, it is looked up on an
association list. This establishes the link between a region and  the  regions  which
are a subset of it at the previous level - i.e.  between a node and its sub-nodes."

	"The  contiguity  scan  is  the  most  complex  program.  It works by leaving
directional pointers in the scratch array.  These are three-bit codes denoting one of
the  eight  possible  neighboring  points. The contiguity scan is always started at a
point which is on the bottom edge of the region. It traces along  this  edge  to  the
right  by  moving  from one marked point to the next, but always keeping an un-marked
point to the right side. As it goes, it erases the marks, so that for a  region  with
smooth  boundaries, it will follow a spiral path to the center, "eating up" the marks
as it goes, like a lathe with the tool continually advancing into the work."

	"As the contiguity routine scans, it lays down back pointers in  the  scratch
array  which  enable  it  to  retrace  its  path back to the start.  If a dead end is
reached (no more marked neighbors), it traces  back  along  this  path,  looking  for
marked  points  to  the  right.  There can be no marked points on the left side while
backtracking, since this was the right side on the way out,  and  the  outgoing  scan
stayed as far to the right as possible.  If a marked point is found on the backtrace,
it is replaced with a pointer to the adjacent path already traced out, and then a new
path  is  traced as if this were a new starting point. When the backtrace reaches the
original starting point, the contiguity  scan  is  completed.   The  effect  of  this
algorithm  is to construct a tree of pointers in the scratch array, with the starting
point at the root. All points which can be reached via  a  connected  path  from  the
starting point will be a part of this tree."